题目描述

$\text{opt} = 1$ 时，代表把一个区间 $l, r$ 内的所有数都 $\text{xor}$ 上 $v$。

$\text{opt} = 2$ 时， 查询一个区间 $[l, r]$ 内选任意个数（包括 $0$ 个）数 $\text{xor}$ 起来，这个值与 $v$ 的最大 $\text{xor}$ 和是多少。

题解

几乎没写过差分，看完这题之后顿时感觉到了差分的强大

首先显然第二个操作需要维护线性基，然后 $O (\log{n})$ 求解

然后因为有 $1$ 操作，所以若是直接维护区间线性基，在计算答案时不知道 $1$ 操作中的 $v$ 在当前答案中被异或上了奇数还是偶数次，故无法求解

但是在单点修改的情景下就不会有上述问题，故现在的问题是如何将区间问题转化为单点问题

于是就需要差分，让每个 $b_{i + 1} = a_{i + 1} ~ \text{xor} ~ a_i$，那么此时 $v$ 的贡献就只作用于 $b_l$ 与 $b_{r + 1}$，可直接单点修改，然后在线段树上同时维护区间线性基，查询时只需查询 $1…l$ 的前缀和（即 $b_l$），再将之与 $l + 1…r$ 的区间线性基合并即可求解答案

复杂度 $O (n \log^2{n})$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <cstdio>
#include <cstring>

#define lson root << 1
#define rson root << 1 | 1

using namespace std;

const int MAXN = 5e04 + 10;

int N, M;
int a[MAXN]= {0};

struct baseSt {
	int b[32];
	int subsum;

	void init () {
		memset (b, 0, sizeof (b));
	}
	void append (int x) {
		for (int j = 31; j >= 1; j --)
			if (x & (1 << (j - 1))) {
				if (! b[j]) {
					b[j] = x;
					break;
				}
				else x ^= b[j];
			}
	}
} ;
baseSt base[MAXN << 2];
baseSt merge (baseSt A, baseSt B) {
	baseSt ret; ret.init ();
	for (int j = 31; j >= 1; j --) {
		if (A.b[j]) ret.b[j] = A.b[j];
		else ret.b[j] = B.b[j];
	}
	for (int j = 31; j >= 1; j --)
		if (A.b[j] && B.b[j])
			ret.append (B.b[j]);
	ret.subsum = A.subsum ^ B.subsum;
	return ret;
}
void build (int root, int left, int right) {
	base[root].init ();
	if (left == right) {
		base[root].subsum = a[left];
		base[root].append (base[root].subsum);
		return ;
	}
	int mid = (left + right) >> 1;
	build (lson, left, mid);
	build (rson, mid + 1, right);
	base[root] = merge (base[lson], base[rson]);
}
void modify (int root, int left, int right, int posi, int delta) {
	if (left == right) {
		base[root].init ();
		base[root].subsum ^= delta, base[root].append (base[root].subsum);
		return ;
	}
	int mid = (left + right) >> 1;
	if (posi <= mid) modify (lson, left, mid, posi, delta);
	else modify (rson, mid + 1, right, posi, delta);
	base[root] = merge (base[lson], base[rson]);
}
baseSt query_base (int root, int left, int right, int L, int R) {
	if (L <= left && right <= R)
		return base[root];
	int mid = (left + right) >> 1;
	baseSt ret; ret.init ();
	if (L <= mid) ret = merge (ret, query_base (lson, left, mid, L, R));
	if (R > mid) ret = merge (ret, query_base (rson, mid + 1, right, L, R));
	return ret;
}
int query_value (int root, int left, int right, int posi) {
	if (left == right)
		return base[root].subsum;
	int mid = (left + right) >> 1;
	if (posi <= mid) return query_value (lson, left, mid, posi);
	else return query_value (rson, mid + 1, right, posi) ^ base[lson].subsum;
}

inline int solve (int x, baseSt A) {
	int ret = x;
	for (int j = 31; j >= 1; j --)
		ret = max (ret, ret ^ A.b[j]);
	return ret;
}

int getnum () {
	int num = 0;
	char ch = getchar ();

	while (! isdigit (ch))
		ch = getchar ();
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return num;
}

int main () {
	N = getnum (), M = getnum ();
	for (int i = 1; i <= N; i ++)
		a[i] = getnum ();
	for (int i = N - 1; i >= 1; i --)
		a[i + 1] ^= a[i];
	build (1, 1, N);
	for (int i = 1; i <= M; i ++) {
		int opt = getnum (), l = getnum (), r = getnum (), x = getnum ();
		if (opt == 1) {
			modify (1, 1, N, l, x);
			if (r < N) modify (1, 1, N, r + 1, x);
		}
		else {
			int delta = query_value (1, 1, N, l);
			if (l == r) printf ("%d\n", max (x ^ delta, x));
			else {
				baseSt bas = query_base (1, 1, N, l + 1, r);
				bas.append (delta);
				printf ("%d\n", solve (x, bas));
			}
		}
	}

	return 0;
}

/*
4 5
1 14 51 4
2 1 3 0
1 2 3 3
2 1 4 10
1 1 4 514
2 3 4 2
*/